import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class BPlusTree {
    public static int count = 0;

    public static void main(String[] args) {
		/*BPlusTree bpt = new BPlusTree(4,new LinkedList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9,10
				,11,12)),new LinkedList<String>(Arrays.asList("a","b","c","d","e","f","g","h","i","j","k","l")));*/
        BPlusTree bPlusTree = new BPlusTree(4, "data.csv");
        System.out.println(bPlusTree.toString());
        Scanner sc = new Scanner(System.in);
        int choice;
        int key;
        String data;
        a:
        while (true) {
            System.out.println("0.quit");
            System.out.println("1.search");
            System.out.println("2.insert");
            System.out.println("3.delete");
            choice = sc.nextInt();
            sc.nextLine();
            switch (choice) {
                case 0:
                    break a;
                case 1:
                    System.out.println("Please input the key you wanna search");
                    key = sc.nextInt();
                    sc.nextLine();
                    System.out.println(bPlusTree.searchValue(key));
                    System.out.println("----------------------cut line------------------------");
                    break;
                case 2:
                    System.out.println("Please input the key and data");
                    key = sc.nextInt();
                    data = sc.nextLine();
                    bPlusTree.insert(key, data);
                    System.out.println(bPlusTree.toString());
                    System.out.println("----------------------cut line------------------------");
                    break;
                case 3:
                    System.out.println("Please input the key you wanna delete");
                    key = sc.nextInt();
                    sc.nextLine();
                    bPlusTree.delete(key);
                    System.out.println(bPlusTree.toString());
                    System.out.println("----------------------cut line------------------------");
                    break;
            }
        }
        sc.close();
    }

    int sonNum;
    Node root;

    BPlusTree(int sonNum, List<Integer> keys, List<String> datas) {

        assert ((datas.size() + 1) / sonNum) > 0.5;
        assert keys.size() == datas.size();
        this.sonNum = sonNum;
        root = new LeafNode(sonNum - 1, null);
        for (int i = 0; i < keys.size(); i++)
            this.insert(keys.get(i), datas.get(i));
    }

    BPlusTree(int sonNum, String path) {
        List<Integer> keys = new ArrayList<>();
        List<String> datas = new ArrayList<>();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File(path)));
            String line = null;
            while ((line = br.readLine()) != null) {
                System.out.println(line);
                String[] keyAndValue = line.split(", ");
                keys.add(Integer.parseInt(keyAndValue[0]));
                datas.add(keyAndValue[1]);
            }
            br.close();
        } catch (IOException e) {
            e.printStackTrace();
        }

        assert ((datas.size() + 1) / sonNum) > 0.5;
        assert keys.size() == datas.size();

        this.sonNum = sonNum;
        root = new LeafNode(sonNum - 1, null);
        for (int i = 0; i < keys.size(); i++)
            this.insert(keys.get(i), datas.get(i));
    }

    @Override
    public String toString() {
        BPlusTree.count = 0;
        StringBuilder sb = new StringBuilder();
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        while (!q.isEmpty()) {
            Node current = q.remove();
            current.count = BPlusTree.count;
            BPlusTree.count++;
            if (current instanceof InternalNode) {
                q.addAll(((InternalNode) current).son);
            }
        }
        q.add(root);
        while (!q.isEmpty()) {
            Node current = q.remove();
            sb.append(current.toString());
            if (current instanceof InternalNode) {
                q.addAll(((InternalNode) current).son);
            }
        }
        return sb.toString();
    }
    //从左向右查找，找到第一个比key大的键它左边的指针指向根节点

    /**
     * 查找叶节点
     *
     * @param key 查找的键
     * @return 键应该在的叶节点
     */
    private LeafNode searchLeaf(int key) {
        Node current = root;
        while (current instanceof InternalNode) {
            InternalNode temp = (InternalNode) current;
            int loc = temp.son.size() - 1;
            for (int i = 0; i < temp.key.size(); i++) {
                if (key < temp.key.get(i)) {
                    loc = i;
                    break;
                }
            }
            current = temp.getSon(loc);
        }
        return (LeafNode) current;
    }

    /**
     * 查找数据
     *
     * @param key 数据的键
     * @return 数据
     */
    public String searchValue(int key) {
        LeafNode temp = this.searchLeaf(key);
        Data result = null;
        for (Data d : temp.data) {
            if (d.key == key) {
                result = d;
                break;
            }
        }
        if (result != null) {
            return result.data;
        } else {
            throw new NullPointerException("no pointer");
        }
    }

    /**
     * 在B+树中插入键和值
     *
     * @param key  要插入的键
     * @param data 要插入的值
     */
    public void insert(int key, String data) {
        LeafNode current = this.searchLeaf(key);
        NodeKey nk = current.insert(key, data);
        InternalNode fatherNode = current.father;
        while (nk != null && fatherNode != null) {
            Node newSon = nk.n;
            nk = fatherNode.insert(nk.key, newSon);
            fatherNode = fatherNode.father;
        }
        if (nk != null) {
            InternalNode newRoot = new InternalNode(this.sonNum, null);
            newRoot.son.add(this.root);
            this.root.father = newRoot;
            newRoot.key.add(nk.key);
            newRoot.son.add(nk.n);
            nk.n.father = newRoot;
            this.root = newRoot;
        }
        //System.out.println(key);
        //System.out.println(this.toString());
    }

    /**
     * 在树中删除元素
     *
     * @param key 要删除的键
     */
    public void delete(int key) {
        Node result;
        LeafNode current = this.searchLeaf(key);
        result = current.delete(key);
        if (result != null)
            this.root = result;
    }
}
